package com.sanra;

import java.util.Random;

/**
 * 二分查找法
 */
public class BinarySearch {

    public static void main(String[] args) {
        int count = 100;
        int scope = 5;
        int[] arr = new int[count];
        Random random = new Random();
        for (int i = 0; i < count; i++) {
            int rd = random.nextInt(scope) + 1;
            if (i == 0) {
                arr[i] = rd;
            } else {
                arr[i] = arr[i - 1] + rd;
            }
        }
        print(arr);
        int p = binarySearch(arr, 33);
        System.out.println(p);

        int pr = binarySearchRecursion(arr, 33, 0, arr.length);
        System.out.println(pr);
    }

    ///非递归实现二分查找
    public static int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (key < arr[mid]) {
                high = mid - 1;
            } else if (key > arr[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static int binarySearchRecursion(int[] arr, int key, int low, int high) {
        if (low <= high) {
            int mid = (low + high) >> 1;
            if (key < arr[mid]) {
                return binarySearchRecursion(arr, key, low, mid - 1);
            } else if (key > arr[mid]) {
                return binarySearchRecursion(arr, key, mid + 1, high);
            } else {
                return mid;
            }
        }
        return -1;
    }

    static void print(int[] arr) {
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
    }
}
